\documentclass[10pt]{article}
\usepackage{amsmath}
\setlength{\parskip}{1ex plus 0.5ex minus 0.2ex}

\newcommand{\problem}[2][No]{\noindent{\sc Problem #1.} #2}
\newcommand{\solution}{\noindent{\sc Solution.}}
\newcommand{\answer}[1]{\noindent{\sc Answer. }#1}
\newcommand{\complexity}{\noindent{\sc Complexity }}
\newcommand{\reference}{\noindent{\sc Reference }}
\newcommand{\seealso}{\noindent{\sc See Also }}

\newcommand{\given}{\,|\,}
\newcommand{\divides}{\,|\,}
\newcommand{\BigO}{\mathcal{O}}

\newcommand{\vl}{\mathbf{l}}

\begin{document}

\problem[187]{Semiprimes}

A composite is a number containing at least two prime factors.  For example, $15 = 3 \times 5$; $9 = 3 \times 3$; $12 = 2 \times 2 \times 3$.

There are ten composites below thirty containing precisely two, not necessarily distinct, prime factors: 4, 6, 9, 10, 14, 15, 21, 22, 25, 26.

How many composite integers, $n < 10^8$, have precisely two, not necessarily distinct, prime factors?

\solution

A semiprime $s=pq$ can be written as the product of two primes $p$,$q$ where $p \le q$. To count the number of semiprimes below a limit, we just to need to count the number of such products.

Let $\pi(x)$ denote the prime-counting function, i.e. it returns the number of primes less than or equal to $x$. Given a prime $p$, the number of products $pq \le N$ where $q$ is prime and $q \ge p$ is 
\[
\pi(N/p) - \pi(p) + 1 .
\]
Therefore the total number of semiprimes is
\[
\sum_p \pi(N/p) - \pi(p) + 1
\]
where $p$ is prime and $2 \le p \le \sqrt{N}$. Note that the largest $\pi(x)$ we need to calculate is $\pi(N/2)$.

In the implementation, we use the Sieve of Eratosthenes method to generate all primes below $N/2$. Then we maintain two iterators $i$ and $j$: $i$ starting from the beginning moving forward and $j$ starting from the end moving backward. For each prime $p_i$, we find the largest $p_j$ such that $p_i p_j < N$. Then the number of semiprimes generated from $p_i$ is $(j-i+1)$. Repeating this process until $i > j$ allows us to compute the total in one pass.

\answer{17427258}

\complexity

Time complexity: $\BigO(n \ln \ln n)$

Space complexity: $\BigO(n)$

\reference

http://en.wikipedia.org/wiki/Sieve\_of\_Eratosthenes

http://en.wikipedia.org/wiki/Prime-counting\_function

\end{document} 